package 数列求值600;

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		int n=20190324;
		if(n<=3) {
			System.out.println(1);
			return;
		}
		int a=1,b=1,c=1;
		for(int i=4;i<=20190324;i++) {
			int tmp=(a+b+c)%10000;
			a=b;
			b=c;
			c=tmp;		
		}
		System.out.println(c);
	}
}
